InforLorV4, Main, Exploration, bibRecord, 00A836

On the Chvátal rank of polytopes in the 0/1 cube

Identifieur interne : 00A836 ( Main/Exploration ); précédent : 00A835; suivant : 00A837

On the Chvátal rank of polytopes in the 0/1 cube

Auteurs : Alexander Bockmayr [France] ; Friedrich Eisenbrand [Allemagne] ; Mark Hartmann [États-Unis] ; Andreas S. Schulz [États-Unis]

Source :

Discrete Applied Mathematics [ 0166-218X ] ; 1999.

RBID : ISTEX:47C7CA1A49D2AFD853FFB32A1720AECD7FE44A39

Descripteurs français

Pascal (Inist)
- Borne supérieure, Cube 0/1, Envéloppe entière, Géométrie, Optimisation combinatoire, Polytope, Polytope dans cube 0/1, Polyèdre, Rang, Rang Chvatal.
mix :
- cutting planes, integer programming, plan de coupe, programmation entière.

English descriptors

KwdEn :
- Chvatal rank, Combinatorial optimization, Cube 0/1, Geometry, Integer hull, Polyhedron, Polytope, Polytope in 01 cube, Rank, Upper bound.
Teeft :
- Absolute value, Bockmayr, Chapel hill, Combinatorial optimization, Convex hull, Cube, Discrete math, Elementary closure, Elsevier science, Induction hypothesis, Inequality, Integer, Integer hull, Integer points, Integral inequalities ax6b, Integral points, Integral polytope, Integral vectors, Main result, Operations research, Polyhedron, Polytope, Polytopes, Rational polyhedra, Rational polytope, Rational polytopes, Salesman problem, Smallest number, Technical report.

Abstract

Abstract: Given a polytope P⊆Rn, the Chvátal–Gomory procedure computes iteratively the integer hull PI of P. The Chvátal rank of P is the minimal number of iterations needed to obtain PI. It is always finite, but already the Chvátal rank of polytopes in R2 can be arbitrarily large. In this paper, we study polytopes in the 0/1 cube, which are of particular interest in combinatorial optimization. We show that the Chvátal rank of any polytope P⊆[0,1]n is O(n3logn) and prove the linear upper and lower bound n for the case P∩Zn=∅.

Url:

DOI: 10.1016/S0166-218X(99)00156-0

Affiliations:

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>On the Chvátal rank of polytopes in the 0/1 cube</title>
<author><name sortKey="Bockmayr, Alexander" sort="Bockmayr, Alexander" uniqKey="Bockmayr A" first="Alexander" last="Bockmayr">Alexander Bockmayr</name>
</author>
<author><name sortKey="Eisenbrand, Friedrich" sort="Eisenbrand, Friedrich" uniqKey="Eisenbrand F" first="Friedrich" last="Eisenbrand">Friedrich Eisenbrand</name>
</author>
<author><name sortKey="Hartmann, Mark" sort="Hartmann, Mark" uniqKey="Hartmann M" first="Mark" last="Hartmann">Mark Hartmann</name>
</author>
<author><name sortKey="Schulz, Andreas S" sort="Schulz, Andreas S" uniqKey="Schulz A" first="Andreas S." last="Schulz">Andreas S. Schulz</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:47C7CA1A49D2AFD853FFB32A1720AECD7FE44A39</idno>
<date when="1999" year="1999">1999</date>
<idno type="doi">10.1016/S0166-218X(99)00156-0</idno>
<idno type="url">https://api.istex.fr/ark:/67375/6H6-DVZ1WGZZ-J/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001090</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001090</idno>
<idno type="wicri:Area/Istex/Curation">001074</idno>
<idno type="wicri:Area/Istex/Checkpoint">002220</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002220</idno>
<idno type="wicri:doubleKey">0166-218X:1999:Bockmayr A:on:the:chvatal</idno>
<idno type="wicri:Area/Main/Merge">00AE87</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:inria-00099018</idno>
<idno type="url">https://hal.inria.fr/inria-00099018</idno>
<idno type="wicri:Area/Hal/Corpus">003739</idno>
<idno type="wicri:Area/Hal/Curation">003739</idno>
<idno type="wicri:Area/Hal/Checkpoint">006605</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">006605</idno>
<idno type="wicri:doubleKey">0166-218X:1999:Bockmayr A:on:the:chvatal</idno>
<idno type="wicri:Area/Main/Merge">00B386</idno>
<idno type="wicri:source">INIST</idno>
<idno type="RBID">Pascal:00-0001592</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000A82</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000000</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000A72</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000A72</idno>
<idno type="wicri:doubleKey">0166-218X:1999:Bockmayr A:on:the:chvatal</idno>
<idno type="wicri:Area/Main/Merge">00B160</idno>
<idno type="wicri:Area/Main/Curation">00A836</idno>
<idno type="wicri:Area/Main/Exploration">00A836</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a">On the Chvátal rank of polytopes in the 0/1 cube</title>
<author><name sortKey="Bockmayr, Alexander" sort="Bockmayr, Alexander" uniqKey="Bockmayr A" first="Alexander" last="Bockmayr">Alexander Bockmayr</name>
<affiliation wicri:level="4"><country xml:lang="fr">France</country>
<wicri:regionArea>Université Henri Poincaré, LORIA, Campus scientifique, B.P. 239, F-54506 Vandoeuvre-lès-Nancy</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
<orgName type="university">Université Henri Poincaré</orgName>
</affiliation>
<affiliation></affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Eisenbrand, Friedrich" sort="Eisenbrand, Friedrich" uniqKey="Eisenbrand F" first="Friedrich" last="Eisenbrand">Friedrich Eisenbrand</name>
<affiliation wicri:level="3"><country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken</wicri:regionArea>
<placeName><region type="land" nuts="2">Sarre (Land)</region>
<settlement type="city">Sarrebruck</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Hartmann, Mark" sort="Hartmann, Mark" uniqKey="Hartmann M" first="Mark" last="Hartmann">Mark Hartmann</name>
<affiliation wicri:level="4"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>University of North Carolina at Chapel Hill, Department of Operations Research, Chapel Hill, NC 27599-3180</wicri:regionArea>
<placeName><region type="state">Caroline du Nord</region>
<settlement type="city">Chapel Hill (Caroline du Nord)</settlement>
</placeName>
<orgName type="university">Université de Caroline du Nord à Chapel Hill</orgName>
</affiliation>
</author>
<author><name sortKey="Schulz, Andreas S" sort="Schulz, Andreas S" uniqKey="Schulz A" first="Andreas S." last="Schulz">Andreas S. Schulz</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>MIT, Sloan School of Management and Operations Research Center, E53-361, Cambridge, MA 02142</wicri:regionArea>
<placeName><region type="state">Massachusetts</region>
</placeName>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">Discrete Applied Mathematics</title>
<title level="j" type="abbrev">DAM</title>
<idno type="ISSN">0166-218X</idno>
<imprint><publisher>ELSEVIER</publisher>
<date type="published" when="1999">1999</date>
<biblScope unit="volume">98</biblScope>
<biblScope unit="issue">1–2</biblScope>
<biblScope unit="page" from="21">21</biblScope>
<biblScope unit="page" to="27">27</biblScope>
</imprint>
<idno type="ISSN">0166-218X</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0166-218X</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Chvatal rank</term>
<term>Combinatorial optimization</term>
<term>Cube 0/1</term>
<term>Geometry</term>
<term>Integer hull</term>
<term>Polyhedron</term>
<term>Polytope</term>
<term>Polytope in 01 cube</term>
<term>Rank</term>
<term>Upper bound</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Borne supérieure</term>
<term>Cube 0/1</term>
<term>Envéloppe entière</term>
<term>Géométrie</term>
<term>Optimisation combinatoire</term>
<term>Polytope</term>
<term>Polytope dans cube 0/1</term>
<term>Polyèdre</term>
<term>Rang</term>
<term>Rang Chvatal</term>
</keywords>
<keywords scheme="Teeft" xml:lang="en"><term>Absolute value</term>
<term>Bockmayr</term>
<term>Chapel hill</term>
<term>Combinatorial optimization</term>
<term>Convex hull</term>
<term>Cube</term>
<term>Discrete math</term>
<term>Elementary closure</term>
<term>Elsevier science</term>
<term>Induction hypothesis</term>
<term>Inequality</term>
<term>Integer</term>
<term>Integer hull</term>
<term>Integer points</term>
<term>Integral inequalities ax6b</term>
<term>Integral points</term>
<term>Integral polytope</term>
<term>Integral vectors</term>
<term>Main result</term>
<term>Operations research</term>
<term>Polyhedron</term>
<term>Polytope</term>
<term>Polytopes</term>
<term>Rational polyhedra</term>
<term>Rational polytope</term>
<term>Rational polytopes</term>
<term>Salesman problem</term>
<term>Smallest number</term>
<term>Technical report</term>
</keywords>
<keywords scheme="mix" xml:lang="fr"><term>cutting planes</term>
<term>integer programming</term>
<term>plan de coupe</term>
<term>programmation entière</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: Given a polytope P⊆Rn, the Chvátal–Gomory procedure computes iteratively the integer hull PI of P. The Chvátal rank of P is the minimal number of iterations needed to obtain PI. It is always finite, but already the Chvátal rank of polytopes in R2 can be arbitrarily large. In this paper, we study polytopes in the 0/1 cube, which are of particular interest in combinatorial optimization. We show that the Chvátal rank of any polytope P⊆[0,1]n is O(n3logn) and prove the linear upper and lower bound n for the case P∩Zn=∅.</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
<li>France</li>
<li>États-Unis</li>
</country>
<region><li>Caroline du Nord</li>
<li>Grand Est</li>
<li>Lorraine (région)</li>
<li>Massachusetts</li>
<li>Sarre (Land)</li>
</region>
<settlement><li>Chapel Hill (Caroline du Nord)</li>
<li>Sarrebruck</li>
<li>Vandœuvre-lès-Nancy</li>
</settlement>
<orgName><li>Université Henri Poincaré</li>
<li>Université de Caroline du Nord à Chapel Hill</li>
</orgName>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Bockmayr, Alexander" sort="Bockmayr, Alexander" uniqKey="Bockmayr A" first="Alexander" last="Bockmayr">Alexander Bockmayr</name>
</region>
<name sortKey="Bockmayr, Alexander" sort="Bockmayr, Alexander" uniqKey="Bockmayr A" first="Alexander" last="Bockmayr">Alexander Bockmayr</name>
</country>
<country name="Allemagne"><region name="Sarre (Land)"><name sortKey="Eisenbrand, Friedrich" sort="Eisenbrand, Friedrich" uniqKey="Eisenbrand F" first="Friedrich" last="Eisenbrand">Friedrich Eisenbrand</name>
</region>
</country>
<country name="États-Unis"><region name="Caroline du Nord"><name sortKey="Hartmann, Mark" sort="Hartmann, Mark" uniqKey="Hartmann M" first="Mark" last="Hartmann">Mark Hartmann</name>
</region>
<name sortKey="Schulz, Andreas S" sort="Schulz, Andreas S" uniqKey="Schulz A" first="Andreas S." last="Schulz">Andreas S. Schulz</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00A836 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00A836 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:47C7CA1A49D2AFD853FFB32A1720AECD7FE44A39
   |texte=   On the Chvátal rank of polytopes in the 0/1 cube
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

Serveur d'exploration sur la recherche en informatique en Lorraine

On the Chvátal rank of polytopes in the 0/1 cube

On the Chvátal rank of polytopes in the 0/1 cube

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.